#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LINE_LENGTH (1 << 20)

char line[LINE_LENGTH];
char line1[LINE_LENGTH];
char line2[LINE_LENGTH];

int hash(const char *str) {
  int res = 0;
  const char *p;
  for (p = str; *p && *p != '\t'; p++)
    res = res * 131 + *p;
  return res;
}

struct record {
  int p;
  int hash_value;
};

FILE *__fin;

int record_cmp(const void *a_, const void *b_) {
  const struct record *a = a_, *b = b_;
  if (a->hash_value != b->hash_value)
    return a->hash_value < b->hash_value ? -1 : +1;
  off_t offset = ftell(__fin);
  fseek(__fin, a->p, SEEK_SET);
  fgets(line1, LINE_LENGTH, __fin);
  fseek(__fin, b->p, SEEK_SET);
  fgets(line2, LINE_LENGTH, __fin);
  fseek(__fin, offset, SEEK_SET);
  return strcmp(line1, line2);
}

#define K 64                     /* pages number */
#define P (1 << 20)              /* page size */
#define S sizeof(struct record)  /* record size */
#define M (P / S)                /* records per page */

int k;
struct record buffer[K][M];
int st[K], ed[K], pt[K];
int heap[K], hn;

#define BUF(i) buffer[i][pt[i]]

int min(int x, int y) {
  return x < y ? x : y;
}

void heap_push(int x) {
  int i, j, y;

  for (i = hn++; i; i = j) {
    j = (i - 1) >> 1;
    y = heap[j];
    if (record_cmp(&BUF(x), &BUF(y)) >= 0)
      break;
    heap[i] = y;
  }
  heap[i] = x;
}

int heap_pop() {
  int i, x, y, z, l, r, res;

  res = heap[0];
  x = heap[--hn];
  i = 0;
  while (1) {
    l = i + i + 1;
    r = i + i + 2;
    z = x;
    if (l < hn) {
      y = heap[l];
      if (record_cmp(&BUF(y), &BUF(z)) < 0)
        z = y;
    }
    if (r < hn) {
      y = heap[r];
      if (record_cmp(&BUF(y), &BUF(z)) < 0)
        z = y;
    }
    if (z == x)
      break;
    heap[i] = z;
    i = (z == heap[l] ? l : r);
  }
  heap[i] = x;

  return res;
}

void merge_sort(FILE * f, FILE * g, int in_place, int u, int v) {
  int pages, d, r, i, j, a, b;

  /* no pages */
  pages = (v - u + M - 1) / M;
  if (pages == 0)
    return;

  /* 1 pages */
  if (pages == 1) {
    if (!in_place) {
      fseek(f, u * S, SEEK_SET);
      fread(buffer[0], S, v - u, f);
      fwrite(buffer[0], S, v - u, g);
    }
    return;
  }

  /* merge sort recursively */
  d = pages / k;
  r = pages % k;
  for (i = 0, a = u; i < k; i++, a = b) {
    b = min(a + (d + (i < r)) * M, v);
    merge_sort(f, g, !in_place, a, b);
  }

  /* swap f, g if needed */
  if (!in_place) {
    FILE *t;
    t = f;
    f = g;
    g = t;
  }

  /* fill buffer */
  for (i = 0, a = u; i < k; i++, a = b) {
    b = min(a + (d + (i < r)) * M, v);

    st[i] = a;
    ed[i] = b;
    pt[i] = 0;

    fseek(g, a * S, SEEK_SET);
    fread(buffer[i], S, min(M, b - a), g);
  }

  /* initialize heap */
  hn = 0;
  for (i = 0; i < k; i++)
    if (st[i] < ed[i])
      heap_push(i);

  /* merge */
  d = 0;
  fseek(f, u * S, SEEK_SET);
  while (u < v) {
    /* copy smallest record to output buffer */
    i = heap_pop();
    buffer[k][d] = BUF(i);

    /* adjust the input buffer */
    st[i]++;
    if (++pt[i] >= M) {
      pt[i] = 0;
      fseek(g, st[i] * S, SEEK_SET);
      fread(buffer[i], S, min(ed[i] - st[i], M), g);
    }
    /* adjust the heap */
    if (st[i] < ed[i])
      heap_push(i);

    /* adjust the output buffer */
    u++;
    if (++d >= M) {
      d = 0;
      fwrite(buffer[k], S, M, f);
    }
  }
  /* write back remaining data */
  fwrite(buffer[k], S, d, f);
}

/* output into single file */
void output(FILE * fo, FILE * f1, FILE * fi, int n) {
  int p, j;

  rewind(fo);
  rewind(f1);

  while (n) {
    p = min(n, M * (k + 1));
    fread(buffer[0], S, p, f1);
    for (j = 0; j < p; j++) {
      fseek(fi, buffer[0][j].p, SEEK_SET);
      fgets(line, LINE_LENGTH, fi);
      fputs(line, fo);
    }
    n -= p;
  }
}

int main(int argc, char **argv) {
  int i, n;
  FILE *fi, *fo, *f1, *f2;

  /* print usage */
  if (argc < 3) {
    printf("usage: %s <infile> <outfile> [options]\n", argv[0]);
    printf("options:\n");
    printf("  -b <buffer-number>      set buffer number, default and maximum value is 130\n");
    return -1;
  }

  /* get arguments */
  k = K;
  for (i = 3; i < argc; i++) {
    if (!strcmp(argv[i], "-b")) {
      sscanf(argv[++i], "%d", &k);
      if (k > K) {
        fprintf(stderr, "error: too many buffer pages.");
        return -1;
      }
    }
  }
  k = k - 1;
  if (k < 2) {
    fprintf(stderr, "error: too few buffer pages.");
    return -1;
  }

  /* open files */
  fi = fopen(argv[1], "rb+");
  if (!fi) {
    fprintf(stderr, "error: file '%s' is not found.\n", argv[1]);
    return -1;
  }
  __fin = fi;  /* for record_cmp() */
  if (!strcmp(argv[1], argv[2])) {
    fprintf(stderr, "error: infile cannot be the same as outfile.\n");
    return -1;
  }
  fo = fopen(argv[2], "wb+");
  f1 = tmpfile();
  f2 = tmpfile();

  /* extract useful data, quick sort pages individualy   */
  struct record *buf = buffer[0];
  for (n = 0; ; n++) {
    if (n != 0 && n % M == 0) {
      qsort(buf, M, S, record_cmp);
      fwrite(buf, S, M, f1);
    }
    buf[n % M].p = ftell(fi);
    if (fgets(line, LINE_LENGTH, fi) == NULL)
      break;
    buf[n % M].hash_value = hash(line);
  }
  if (n % M != 0) {
    qsort(buf, n % M, S, record_cmp);
    fwrite(buf, S, n % M, f1);
  }

  /* merge sort */
  merge_sort(f1, f2, 1, 0, n);

  /* output from useful data to real data */
  output(fo, f1, fi, n);

  /* close files */
  fclose(f1);
  fclose(f2);
  fclose(fi);
  fclose(fo);

  return 0;
}
